import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-09-24
 * Time: 23:00
 */
//BFS
class Solution7 {
    int[] dx = {0,0,-1,1};
    int[] dy = {-1,1,0,0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int m = image.length;
        int n = image[0].length;
        int num = image[sr][sc];

        if(num == color) {
            return image;
        }

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{sr,sc});

        while(!queue.isEmpty()) {
            int[] t = queue.poll();
            int a = t[0], b = t[1];
            image[a][b] = color;
            for(int i = 0; i < 4; i++) {
                int x = a+dx[i],y =b+dy[i];
                if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == num) {
                    queue.add(new int[]{x,y});
                }
            }
        }
        return image;
    }
}